//
//  BinarySearchTree.swift
//  DataStructureAndAlgorithm
//
//  Created by icemelon on 2021/8/5.
//

import Foundation


class BinarySearchTree<T: Comparable> : BinaryTree<T> {
    
    enum BinarySearchTreeOrderType {
        case Preord
        case Inorder
        case Postorder
        case LevelOrder
    }
    
    var comparsion: ComparisonResult! //默认是升序
    //    init(com: ComparisonResult? = .orderedAscending) {
    init(com: ComparisonResult? = .orderedAscending) {
        self.comparsion = com!
    }
    
    func add(element: T) {
        if root == nil {
            root = Node<T>(element: element)
            afterAdd(node: root!)
        }
        else {
            var node = root
            var parent = root
            var cmp = 0
            while node != nil {
                parent = node
                cmp = compare(element1: element, element2: (node?.element)!)
                if cmp < 0 {
                    node = node?.left
                }
                else if cmp > 0 {
                    node = node?.right
                }
                else {
                    print("相等")
                    return
                }
            }
            node = Node(element: element, parent: parent)
            
            if cmp < 0 {
                parent?.left = node
            }
            else if cmp > 0 {
                parent?.right = node
            }
            afterAdd(node: node!)
            
        }
        size += 1
       
    }
    
    //为了avl树和红黑树的继承
    //如果添加顺序是递增或者递减，就会导致时间复杂度由O（logn）变为O（n）,所以AVL 红黑要自平衡
    func afterAdd(node: Node<T>) {
         
    }
    
    func remove(element: T) {
        if var node = getNode(by: element) {
            if node.isRoot() {
                root = nil
                size = 0
                self.afterRemove(node: node) //如果是根节点那么 一定是平衡的 暂时先调用
                return
            }
            
            if node.hasTwoChildren() {//如果是度为2的  就找到前驱或者后继来删除
                let pre = node.predecessor()
                node.element = pre!.element
                
                node = pre!
            }
            
            if node.hasSingleChild() {// 删除度为1 的节点
                let nodeChild = node.left != nil ? node.left : node.right
                nodeChild!.parent = node.parent
                
                if node.isLeft() {
                    node.parent?.left = nodeChild!
                }
                else {
                    node.parent?.right = nodeChild!
                }
                
                self.afterRemove(node: node)
            }
            else { //叶子节点  直接删除叶子节点
                if node.isRight() { // 如果是前驱节点 那么一定是right
                    node.parent?.right = nil
                }
                else {
                    node.parent?.left = nil
                }
                self.afterRemove(node: node)
            }
            size -= 1
        }
        else {
            print("未找到节点")
        }
    }
    
    func afterRemove(node: Node<T>) {
        
    }
    
    func contains(element: T) -> Bool {
        if getNode(by: element) != nil {
            return true
        }
        return false
    }
    
    private func getNode(by element: T) -> Node<T>? {
        var node = root
        while node != nil {
            let cmp = compare(element1: element, element2: node!.element)
            if cmp == 0 {
                return node
            }
            else if cmp < 0 {
                node = node?.left
            }
            else {
                node = node?.right
            }
        }
        return nil
    }
    //遍历
    fileprivate func traverse(by type: BinarySearchTreeOrderType? = .Preord,map: ((_ item: Node<T>) -> Bool?)? = nil) {
        switch type {
        case .Preord:
            self.preord(node: root, map: map)
        case .Inorder:
            self.inorder(node: root, map: map)
        case .Postorder:
            self.postorder(node: root, map: map)
        default:
            self.levelOrder(node: root, map: map)
        }
        print("---------- \n")
    }
    
    //-1位循环获取left 1位循环获取right  如果为升序 则为左边小 则通过<去判断 e1和e2
    private func compare(element1: T, element2: T) -> Int {
        switch comparsion {
        case .orderedAscending, .orderedSame:
            if element1 == element2 {return 0}
            return element1 < element2 ? -1 : 1
        default:
            if element1 == element2 {return 0}
            return element1 > element2 ? -1 : 1
        }
    }
    
}

extension BinarySearchTree {
    //树的高度
    func height() -> Int {
        return printTree(isGetHeight: true)!
    }
}


//遍历 打印树 树的高度
extension BinarySearchTree {
    //中 左 右
    private func preord(node: Node<T>?, map: ((_ item: Node<T>) -> Bool?)? = nil) {
        guard  node != nil else {
            return
        }
        if map != nil {
            let stop = map!(node!)
            if stop != nil, stop! {
                return
            }
        }
        else {
            print(node!.element)
        }
        preord(node: node?.left, map: map)
        preord(node: node?.right, map: map)
    }
    //中序遍历打印的结果 是升序或者降序  左 中 右
    private func inorder(node: Node<T>?, map: ((_ item: Node<T>) -> Bool?)? = nil) {
        guard  node != nil else {
            return
        }
        inorder(node: node?.left, map: map)
        if map != nil {
            let stop = map!(node!)
            if stop != nil, stop! {
                return
            }
        }
        else {
            print(node!.element)
        }
        inorder(node: node?.right, map: map)
    }
    //左 右 中
    private func postorder(node: Node<T>?, map: ((_ item: Node<T>) -> Bool?)? = nil) {
        guard  node != nil else {
            return
        }
        
        postorder(node: node?.left, map: map)
        postorder(node: node?.right, map: map)
        if map != nil {
            let stop = map!(node!)
            if stop != nil, stop! {
                return
            }
        }
        else {
            print(node!.element)
            
        }
    }
    //通过队列实现
    private func levelOrder(node: Node<T>?, map: ((_ item: Node<T>) -> Bool?)? = nil) {
        guard  node != nil else {
            return
        }
        var queue = Queue<Node<T>>()
        
        queue.enquequ(element: node!)
        while !queue.isEmpty() {
            
            let popN = queue.front()
            queue.dequeue()
          
            if map != nil {
                let stop = map!(popN!)
                if stop != nil, stop! {
                    return
                }
            }
            else {
                print(popN!.element)
            }
            
            if popN?.left != nil {
                queue.enquequ(element: popN!.left!)
            }
            if popN?.right != nil {
                queue.enquequ(element: popN!.right!)
            }
            
        }
        
    }
    //将获取树的高度和打印放在一个函数
    @discardableResult func printTree(isGetHeight: Bool? = false) -> Int? {
        guard  root != nil else {
            if isGetHeight != nil, isGetHeight! { return 0 }
            else {
                print("tree count = 0")
                return nil
            }
        }
        var queue = Queue<Node<T>>()
        queue.enquequ(element: root!)
        var levelCount = 1
        var printStr = ""
        var height = 0
        while !queue.isEmpty() {
            let popN = queue.front()
            queue.dequeue()
            levelCount -= 1
            printStr += "\(popN!.element)(\(popN!.height))"
            if popN?.left != nil {
                queue.enquequ(element: popN!.left!)
            }
            if popN?.right != nil {
                queue.enquequ(element: popN!.right!)
            }
            if levelCount == 0 {
                printStr += "\n"
                levelCount = queue.count
                height += 1
            }
        }
        if isGetHeight != nil, isGetHeight! { return height }
        else {
            print("tree is: \n\(printStr)")
            print("==============size:\(size) height: \(self.height()) \n\n")
            return nil
        }
        
    }
}


extension BinarySearchTree {
    class func testTree() {
        let data = [7, 4, 9, 2, 5, 8, 11, 3, 12, 1]
//                let data = [7, 4, 9, 7]
        let tree = BinarySearchTree<Int>(com: .orderedAscending)
        for item in data {
            tree.add(element: item)
//            tree.printTree()
        }
        
        let removeData = [4, 9, 11, 1]
        for item in removeData {
            tree.remove(element: item)
            tree.printTree()
        }
 
//        tree.traverse(by: .Preord)
//        tree.traverse(by: .Inorder)
//        tree.traverse(by: .Postorder)
//        tree.traverse(by: .LevelOrder)
        
//        tree.traverse(by: .LevelOrder)  { item in
//            print(item)
//        }
   
    }
}
